package leetcode101.binary_search;

/**
 * @author Synhard
 * @version 1.0
 * @Class Code5
 * @Description 540. Single Element in a Sorted Array
 * You are given a sorted array consisting of only integers where every element appears exactly twice,
 * except for one element which appears exactly once. Find this single element that appears only once.
 *
 * Follow up: Your solution should run in O(log n) time and O(1) space.
 *
 * Example 1:
 *
 * Input: nums = [1,1,2,3,3,4,4,8,8]
 * Output: 2
 * Example 2:
 *
 * Input: nums = [3,3,7,7,10,11,11]
 * Output: 10
 * Constraints:
 *
 * 1 <= nums.length <= 10^5
 * 0 <= nums[i] <= 10^5
 *
 * @tel 13001321080
 * @email 823436512@qq.com
 * @date 2021-03-29 10:26
 */
public class Code5 {
    public static void main(String[] args) {
        int[] arr = {3,3,7,7,10,11,11};
        System.out.println(singleNonDuplicate(arr));
    }

    public static int singleNonDuplicate(int[] arr) {
        int low = 0, high = arr.length - 1, mid;
        while (low < high) {
            mid = low + ((high - low) >> 1);
            if (arr[mid] != arr[mid - 1] && arr[mid] != arr[mid + 1]) {
                return arr[mid];
            }
            if (arr[mid] == arr[mid - 1]) { // 如果mid的值和左边的相等
                /*
                如果mid右半边的数据刚好是偶数，说明target在mid的左边
                 */
                if (((high - mid) & 1) == 0) {
                    high = mid;
                } else {
                    low = mid + 1;
                }
            } else { // 如果mid的值和右边的相等
                /*
                如果mid左半边的数据刚好是偶数，说明target在mid的右边
                 */
                if (((mid - high) & 1) == 0) {
                    low = mid;
                } else {
                    high = mid - 1;
                }
            }
        }
        return arr[low];
    }
}
